package com.zz.array;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 张哲
 * @email a252013135@163.com
 * @date 2024/9/12 13:35
 * <p>
 * 在⼀个⻓度为 n 的数组⾥的所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的，但不
 * 知道有⼏个数字是重复的。也不知道每个数字重复⼏次。请找出数组中第⼀个重复的数字。 例如，如果
 * 输⼊⻓度为 7 的数组 [2,3,1,0,2,5,3]，那么对应的输出是第⼀个重复的数字 2。没有重复的数
 * 字返回 -1。
 * <p>
 * 输⼊
 * [ 2, 3, 1, 0, 2, 5, 3 ]
 * <p>
 * 返回值
 * 2
 */
public class Offer3 {

    /**
     * 通过Set集合解决
     *
     * @param numbers
     * @return
     */
    public int duplicate1(int[] numbers) {
        if (numbers.length == 0 || numbers.length == 1) {
            return -1;
        }
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < numbers.length; i++) {
            boolean flag = set.add(numbers[i]);
            if (!flag) {
                return numbers[i];
            }
        }
        return -1;
    }

    /**
     * 通过双重遍历解决
     *
     * @param numbers
     * @return
     */
    public int duplicate2(int[] numbers) {
        if (numbers.length == 0 || numbers.length == 1) {
            return -1;
        }
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if(numbers[j] == numbers[i]){
                    return numbers[i];
                }
            }
        }
        return -1;
    }


    /**
     * 计数法，根据数组中所有数据大小为0~n-1得出可以使用另一个数组来记录某个数据出现的次数，只要第二次出现了则返回
     * @param numbers
     * @return
     */
    public int duplicate3(int[] numbers) {
        if (numbers != null) {
            int[] nums = new int[numbers.length];
            for (int i = 0; i < numbers.length; i++) {
                if (nums[numbers[i]] == 1) {
                    return numbers[i];
                } else {
                    nums[numbers[i]] = 1;
                }
            }
        }
        return -1;

    }
}
